package 平衡二叉树;


public class 平衡二叉树 {
	public static void main(String[] args) {
		
		//原始二叉树
		
		//左旋--右右高
//		int arr[] = {4,3,6,5,7,8};
		//右旋--左左高
//		int arr[] = {8,6,9,5,7,4};
		//双旋--左右高、右左高，就是一次旋转不能得到平衡二叉树，(?因为在子树中存在相反方向的高低树(一侧高于另一侧)?)
		//先左、右旋转一次，得到左左、右右，然后再旋转
		/*
		 * 			10                 10				8
		 * 		   /  \				  / \			   / \
		 * 		  7    11            8  11 			  7  10 	
		 * 		 / \   				/ \				 /   / \
		 * 		6   8              7  9				6	9  11   
		 *           \            /
		 *            9          6   
		 */
		int arr[] = {10,11,7,6,8,9};
		
		AVLTree avlTree = new AVLTree();
		for(int i = 0; i < arr.length; i++) {
			avlTree.add(new Node(arr[i]));
		}
		 
		avlTree.midOrder();
		System.out.println("树高度："+avlTree.root.height());
		System.out.println("左子树高度："+avlTree.root.leftHeight());
		System.out.println("右子树高度："+avlTree.root.rightHeight());
		System.out.println("root"+avlTree.root);
		
	}
}


/**
 * 二叉排序树
 * @author PC
 *
 */
class AVLTree {
	//根节点
	public Node root;
	
	/**
	 *  添加结点
	 * @param node
	 */
	public void add(Node node) {
		
		if(root == null) {
			//初始时根节点是空的，此时将第一个结点赋给根节点
			root = node;
		}else {
			//从根节点向后面一个一个添加
			root.add(node);
		}
	}
	
	
	/**
	 *  中序遍历
	 */
	public void midOrder() {
		if(root == null) {
			System.out.println("空树...");;
		}else {
			root.midOrder();
		}
	}
	
	/**
	 *  查找要删除结点
	 * @param value
	 */
	public Node search(int value) {
		if(root == null) {
			return null;
		}else {
			return root.search(value);
		}
	}
	
	/**
	 *  查找要删除结点的父结点
	 * @param value
	 */
	public Node searchParent(int value) {
		if(root == null) {
			return null;
		}else {
			return root.searchParent(value);
		}
	}
	
	/**
	 *  删除，分为三种情况
	 * @param value
	 */
	public void delNode(int value) {
		
		
		//待删除结点
		Node targetNode;
		//待删除结点父结点
		Node parent;
		if(root == null) {
			return;
		}else {
			//1、首先找到待删除结点
			targetNode = search(value);
			if(targetNode == null) {
				//没找到
				return;
			}
			//如果这棵树只有一个根节点
			if(root.left == null && root.right == null) {
				root = null;
				return;
			}
		}
		
		//2、找到待删除结点的父结点
		parent = searchParent(value);
		
		//3、判断删除时的三种情况
		
		//1)待删除结点是叶子结点
		if(targetNode.left == null && targetNode.right == null) {
			//判断targetNode是父结点的哪个孩子
			if(parent.left != null && parent.left.value == value) {
				//是左孩子
				parent.left = null;
			}else if(parent.right != null && parent.right.value == value) {
				//是右孩子
				parent.right = null;
			}
		}else if(targetNode.left != null && targetNode.right != null) {
			
			//3)待删除结点有两颗子树(子树包括两个结点)
			//3.1查找右子树里面最小结点
			int minVal = delRightTreeMin(targetNode.right);
			//3.2将最小节取出然后删除，替换到当前结点
			targetNode.value = minVal;
			
		}else {
			
			//2)待删除结点有一棵子树(一棵子树包括多个结点)
			//2.1如果待删除结点有左子结点
			if(targetNode.left != null) {
				//注意！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
				//并且待删除结点是根节点，且只有一个孩子，此时调用parent.left可能出错，如{7,3}
				if(parent != null) {
					//2.1.1如果待删除结点是左孩子
					if(parent.left.value == value) {
						parent.left = targetNode.left;
					}else {
						parent.right = targetNode.left;
					}
				}else {
					//arr={7,3}这种情况
					root = targetNode.left;
				}
			}else {
				//2.2如果待删除结点有右子结点
				//并且待删除结点是根节点，且只有一个孩子，此时调用parent.left可能出错，如{7,3}
				if(parent != null) {
					//2.2.1如果待删除结点是左孩子
					if(parent.left.value == value) {
						parent.left = targetNode.right;
					}else {
						parent.right = targetNode.right;
					}
				}else {
					//arr={7,3}这种情况
					root = targetNode.right;
				}
			}
		}
	}
	
	/**
	 *  找到以这个结点为根的树中最小结点，删除并返回
	 * @param node
	 * @return
	 */
	public int delRightTreeMin(Node node) {
		Node target = node;
		//向左找最小结点，就是最左边最后一个
		while(target.left != null) {
			target = target.left;
		}
		//删除这个最小结点，并返回
		delNode(target.value);
		return target.value;
	}
}


/**
 * 结点
 * @author PC
 *
 */
class Node{
	public int value;
	public Node left;
	public Node right;
	public Node(int value) {
		super();
		this.value = value;
	}
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
	
	/**
	 *  添加
	 * @param node
	 */
	public void add(Node node) {
		
		if(node == null) {
			return;
		}
		
		//不为空，判断传入结点大小，小在左，大在右
		if(node.value < this.value) {
			//当前结点大，新结点小，放左边
			if(this.left == null) {
				this.left = node;
			}else {
				//不为空，递归放到下一个结点左边
				this.left.add(node);
			}
		}else {
			//大于或等于都放右边
			if(this.right == null) {
				this.right = node;
			}else {
				this.right.add(node);
			}
		}
		
		//添加一个就判断是否符合平衡二叉树，注意：再添加时，this永远都是root在添加，所以不论在谁的
		//位置上不平衡了，都是从root根开始旋转的！！！！！！！！！！！！！！！！！！！！！！！！！！！！
		
		//添加双旋转
		
		//如果右边高，左边低，向左旋--左低--右右高
		if(this.rightHeight()-this.leftHeight() > 1) {
			
			//右左高
			//--右子的左子高，如果一棵树有右子树，右子树又有左、右子树，并且左子树高度大于右子树，需要先右旋，再左旋
			if(this.right != null && this.right.leftHeight() > this.right.rightHeight()) {
				//先右旋
				this.right.rightRotate();
				//再左旋
				this.leftRotate();
			}else {
				
				//如果左旋时不存在 右树的左子树高，则直接左旋
				this.leftRotate();
			}
			//结束直接返回，
			return;
		}
		
		//如果左边高，右边低，向右旋--右低--左左高
		if(this.leftHeight() - this.rightHeight() > 1){
			
			//左右高
			//--左子的右子高，如果一棵树有左子树，左子树又有左、右子树，且右子树高于左子树，先左旋，在右旋
			if(this.left != null && this.left.rightHeight()>this.left.leftHeight()) {
				//先左旋
				this.left.leftRotate();
				//再右旋
				this.rightRotate();
			}else {
				
				//如果右旋时不存在 左树的右子树高，则直接右旋
				this.rightRotate();
			}
		}
	}
	
	/**
	 *  中序遍历
	 */
	public void midOrder() {
		
		if(this.left != null) {
			this.left.midOrder();
		}
		System.out.println(this);
		if(this.right != null) {
			this.right.midOrder();
		}
	}
	
	/**
	 *  获取左子树高度
	 * @return
	 */
	public int leftHeight() {
		if(left == null) {
			return 0;
		}
		return left.height();
	}
	
	/**
	 *  获取右子树高度
	 * @return
	 */
	public int rightHeight() {
		if(right == null) {
			return 0;
		}
		
		return right.height();
	}
	
	/**
	 *  返回以改点为子树的高度
	 * @return
	 */
	public int height() {
		//在树中可以这样写
//		if(root == null) {
//			return 0;
//		}
//		int lHeight = root.left.height();
//		int rHeight = root.right.height();
//		int max = Math.max(lHeight, rHeight);
//		return max+1;
		
		//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		//结点为空返回高度0，否则递归求高，然后+1算出该节点总高度
		//真正执行计算的是最后的+1，因为从开始时从上向下递归，只有进入方法，其实没有进行+1，只有到达最后一层
		//方法结束，从低向上返回时才进行+1计算高度，可以输出this和返回值进行查看
//		int i = 0;
//		System.out.println(this+"-"+i);
//		i = Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
//		System.out.println(this+"--"+i);
		return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
	}
	
	
	/**
	 *  左旋转
	 */
	public void leftRotate() {
		
		//创建新的结点，值等于当前结点----------------------把根节点提出来
		Node newNode = new Node(this.value);
		//把新结点的左子树设置为当前结点的左子树-------------把旧的左子树提出来
		newNode.left = this.left;
		//把新结点的右子树设置为当前结点的右子树的左子树------(如果左旋，右边第一个子结点变根节点，原本有两个结点，现在把其中一个提出来)
		newNode.right = this.right.left;
		//把当前结点的值设为当前结点的右结点的值-------------把右子结点提到上一层，向左旋转
		this.value = this.right.value;
		//把当前结点的右子树设置为当前结点的右子树的右子树----左旋之后，右边空一个，把下下面一个提上来
		this.right = this.right.right;
		//把当前结点的左子树设置为新节点---------------------把新节点放到跟的左边，左旋完成
		this.left = newNode;
	}
	
	/**
	 *  右旋
	 */
	public void rightRotate() {
		//创建新结点，值为当前结点
		Node newNode = new Node(this.value);
		//把新节点右子树设为当前结点的右子树
		newNode.right = this.right;
		//把新结点的左子树设为当前结点的左子树的右子树
		newNode.left = this.left.right;
		//当前结点的值为当前结点的左结点的值
		this.value = this.left.value;
		//当前结点的左结点设为当前结点做节点的左结点
		this.left = this.left.left;
		//当前结点的右子树为新结点
		this.right = newNode;
	}
	
	/**
	 *  查找要删除的结点
	 * @param value
	 * @return
	 */
	public Node search(int value) {
		
		//如果当前结点就是要删除的结点，就返回，下面已经判断过null了
		if(this.value == value) {
			return this;
		}
		
		//如果要删除结点小于当前结点
		if(this.value > value) {
			if(this.left == null) {
				return null;
			}
			return this.left.search(value);
		}else {
			//大于或等于
			if(this.right == null) {
				return null;
			}
			return this.right.search(value);
		}
	}
	
	/**
	 *  查找要删除结点父结点
	 * @param value
	 * @return
	 */
	public Node searchParent(int value) {
		//如果当前结点是要删除的结点，就返回，注意一个父节点有两个子结点，都要判断
		if((this.left != null && this.left.value == value) 
				|| (this.right != null && this.right.value == value)) {
			return this;
		}
		
		//如果查找结点小于当前结点，向左递归找，并且左边不为空
		if(this.value > value && this.left != null) {
			//小于
			return this.left.searchParent(value);
		}else if(this.value <= value && this.right != null){
			//大于等于
			return this.right.searchParent(value);
		}else {
			//没找到
			return null;
		}
	}
}